package com.study.lxy.security;

import org.junit.Test;

import java.io.FileInputStream;
import java.util.*;

public class TreeSetTest {

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(new FileInputStream("D:/data.txt"));
        String title = sc.nextLine();
        String[] totals = title.split(" ");
        int totalAmt = Integer.valueOf(totals[0]);
        int itemCount = Integer.valueOf(totals[1]);

        List<Item> itemList = new ArrayList<Item>();
        Item prev = null;
        for(int i = 0;i < itemCount; i++){
            String s = sc.nextLine();
            String[] ele = s.split(" ");
            Item item = new Item(Integer.valueOf(ele[0]),Integer.valueOf(ele[1]),Integer.valueOf(ele[2]));
            //System.out.println(item);
            if("1".equals(ele[2])){
                prev.addFollow(item);
            } else {
                itemList.add(item);
                System.out.println("add item : " + item);
                prev = item;
            }
        }
        Collections.sort(itemList,new Comparator<Item>(){
            public int compare(Item i1, Item i2){
                Float f1 = 1.0f * i1.getMutipy() / i1.getTotalAmt();
                Float f2 = 1.0f * i2.getMutipy() / i2.getTotalAmt();
                return f2.compareTo(f1);
            }
        });
        System.out.println("add success, size = " + itemList.size());
        int lestAmt = totalAmt;
        int totalMutipy = 0;
        // 实际上没这么简单，还要考虑剩余金额的问题。优先重要程度高的方案不一定是最优解
        // 如果使用穷举法，算法的耗时太高了
        for(Item item : itemList){
            System.out.println(item);
            if(item.getTotalAmt() <= lestAmt){
                totalMutipy += item.getMutipy();
                lestAmt -= item.getTotalAmt();
            }
        }
        System.out.println(totalMutipy);

    }

    private static class Item{
        private int amt;
        private int lvl;
        private int isFollow;
        private List<Item> follows = new ArrayList<Item>();

        public Item(int amt, int lvl,int isFollow){
            this.amt = amt;
            this.lvl = lvl;
            this.isFollow = isFollow;
        }

        public int getAmt(){
            return amt;
        }

        public void addFollow(Item follow){
            follows.add(follow);
        }

        public int getTotalAmt(){
            int totalAmt = amt;
            for(Item follow : follows){
                totalAmt += follow.getAmt();
            }
            return totalAmt;
        }

        public int getMutipy(){
            int mutipy = amt * lvl;
            for(Item follow : follows){
                mutipy += follow.getMutipy();
            }
            return mutipy;
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Item{");
            sb.append("amt=").append(amt);
            sb.append(", mutipy=").append(getMutipy());
            sb.append(", lvl=").append(lvl);
            sb.append(", isFollow=").append(isFollow);
            sb.append(", follows=").append(follows);
            sb.append('}');
            return sb.toString();
        }
    }

    @Test
    public void test2() throws Exception{
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String point = "ADWS";
        String steps[] = line.split(";");

        int x = 0,y = 0;
        for(String step : steps){
            // 判断是否是有效的操作
            if(step.length() <2 || step.length() > 3){
                continue;
            }
            String p = step.substring(0,1);
            String num = step.substring(1);
            try{
                int val = Integer.valueOf(num);
                if("A".equals(p)){
                    x -= val;
                } else if("D".equals(p)){
                    x += val;
                } else if("W".equals(p)){
                    y += val;
                } else if("S".equals(p)){
                    y -= val;
                } else {
                    continue;
                }
            } catch(Exception e){
                continue;
            }

        }
        System.out.println(x + "," + y);
    }

}
